package ai.zixing.mashibing.advance_class.first.class05;

/**
 * 最长回文子串
 */
public class Code01_Manacher {

    public static int manacher(String s) {
        if (s == null || s.isEmpty()) {
            return 0;
        }
        // 添加虚轴
        char[] str = manacherString(s);
        // 回文半径的大小
        int[] pArr = new int[str.length];
        // R 更新，C 一定更新
        // 更新点
        int C = -1;
        // 更新点扩到的右边界,第一个失败的位置
        int R = -1;
        // 记录最长回文
        int max = Integer.MIN_VALUE;
        // 第一次进来 i 一定在在 R 外
        // for：每个位置都要扩
        for (int i = 0; i < str.length; i++) {
            // R 第一个违规的位置,即 i >= R 表示 i 在 R 外，i位置本身回文是 1，不需要验证
            // R > i，表示 i 在 R 内； 2 * C - i 就是 i 的对称点
            // i 在 R 内，有三种情况，范围小的不需要验证
            // i位置扩出来的答案，i位置扩的区域，至少是多大
            pArr[i] = R > i ? Math.min(pArr[2 * C - i], R - i) : 1;
            // 左右侧不越界，则暴力往外扩
            while (i + pArr[i] < str.length && i - pArr[i] > -1) {
                // 可以继续扩，回文半径++
                if (str[i + pArr[i]] == str[i - pArr[i]]) {
                    pArr[i]++;
                } else {
                    // 不想等，直接跳出
                    break;
                }
            }
            // 有没有刷新右边界，如果刷新R,则更新 R、C
            if (i + pArr[i] > R) {
                R = i + pArr[i];
                C = i;
            }
            max = Math.max(max, pArr[i]);
        }
        return max - 1;
    }

    private static char[] manacherString(String s) {
        char[] charArr = s.toCharArray();
        char[] ans = new char[charArr.length * 2 + 1];
        int index = 0;
        for (int i = 0; i < ans.length; i++) {
            // 奇数位补 '#'
            ans[i] = (i & 1) == 0 ? '#' : charArr[index++];
        }
        return ans;
    }

    private static int right(String s) {
        if (s == null || s.isEmpty()) {
            return 0;
        }
        char[] str = manacherString(s);
        int max = 0;
        for (int i = 0; i < str.length; i++) {
            int L = i - 1;
            int R = i + 1;
            while (L >= 0 && R < str.length && str[L] == str[R]) {
                L--;
                R++;
            }
            max = Math.max(max, R - L - 1);
        }
        return max / 2;
    }

    public static String getRandomString(int possibilities, int size) {
        char[] ans = new char[(int) (Math.random() * size) + 1];
        for (int i = 0; i < ans.length; i++) {
            ans[i] = (char) ((int) (Math.random() * possibilities + 'a'));
        }
        return String.valueOf(ans);
    }

    public static void main(String[] args) {
        int possibilities = 5;
        int strSize = 20;
        int testTime = 200000;
        System.out.println("begin test");
        for (int i = 0; i < testTime; i++) {
            String str = getRandomString(possibilities, strSize);
            if (manacher(str) != right(str)) {
                System.out.println("error");
            }
        }
        System.out.println("test end");
//        String str = "1212";
//        System.out.println(manacher(str));
//        System.out.println(right(str));
    }

}
